// 层序遍历需要使用一个队列来存储有用的节点。整体的思路如下：

// 将 root 放入队列
// 取出队首元素，将 val 放入返回的数组中
// 检查队首元素的子节点，若不为空，则将子节点放入队列
// 检查队列是否为空，为空，结束并返回数组；不为空，回到第二步
// 时间复杂度和空间复杂度是 O(N)。代码实现如下：
// 在 Js 中没有专门的“队列”，都使用数组来实现。队列的常用操作：

// 入队：array.push(val)
// 出队：array.shift()
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
var levelOrder = function (root) {
    if (!root) return [];
    var queue = [];//数组实现队列存储节点
    var result = [];
    queue.push(root);//将第一个节点插入队列
    while (queue.length !== 0) {
        let a = queue.shift();//取出队首元素
        result.push(a.val);

        if (a.left) {
            queue.push(a.left);
        }
        if (a.right) {
            queue.push(a.right);
        }
    }
    return result;

};

